package array

func SortColors(nums []int) {
	colorMap := map[int]int{}

	for _, v := range nums {
		if _, ok := colorMap[v]; ok {
			colorMap[v]++
		}
		colorMap[v] = 1
	}

	index := 0
	for _, i := range []int{0, 1, 2} {
		if v, ok := colorMap[i]; ok {
			for j := 0; j < v; j++ {
				nums[index+j] = i
			}
			index += v
		}
	}

}

// 单指针解法
func SortColors2(nums []int) {
	countTarget_0 := sortColor_helper(nums, 0)
	sortColor_helper(nums[countTarget_0:], 1) // 传递的切片的nums[countTarget]为第0位
}

func sortColor_helper(nums []int, target int) (countTarget int) {
	for i, v := range nums {
		if v == target {
			nums[i], nums[countTarget] = nums[countTarget], nums[i]
			countTarget++
		}
	}

	return countTarget
}

// 双指针解法1
func sortColors2(nums []int) {
	p0, p1 := 0, 0

	for i, v := range nums {
		if v == 0 {
			nums[i], nums[p0] = nums[p0], nums[i]
			if p0 < p1 {
				nums[p1], nums[i] = nums[i], nums[p1]
			}
			p0++
			p1++
		} else if v == 1 {
			nums[i], nums[p1] = nums[p1], nums[i]
			p1++
		}
	}

}

// 双指针解法3
func sortColors3(nums []int) {
	p0, p2 := 0, len(nums)-1
	for i := 0; i <= p2; i++ {
		for ; i <= p2 && nums[i] == 2; p2-- {
			nums[i], nums[p2] = nums[p2], nums[i]
		}

		if nums[i] == 0 {
			nums[i], nums[p0] = nums[p0], nums[i]
			p0++
		}
	}
}
